package com.cyan.learn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * 二叉树算法
 */
public class TreeTest {
    /**
     * 144丶二叉树的前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        preOrder(list, root);
        return list;
    }

    private void preOrder(ArrayList<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }

        list.add(root.val);
        preOrder(list, root.left);
        preOrder(list, root.right);
    }

    /**
     * 145丶二叉树的后序遍历
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        postOrder(list, root);
        return list;
    }

    private void postOrder(ArrayList<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }

        postOrder(list, root.left);
        postOrder(list, root.right);
        list.add(root.val);
    }


    /**
     * 94丶二叉树的中序遍历
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        inOrder(list, root);
        return list;
    }

    private void inOrder(ArrayList<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(list, root.left);
        list.add(root.val);
        inOrder(list, root.right);
    }


    /**
     * 102丶二叉树的层序遍历
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }

        // 辅助队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelList = new ArrayList<>();

            while (size > 0) {
                size--;
                TreeNode node = queue.pop();
                levelList.add(node.val);
                if (node.left != null) {
                    queue.add(node.left); // 队尾加元素
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            lists.add(levelList);
        }

        return lists;
    }

    /**
     * 226丶反转二叉树
     * 层序遍历
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode node = queue.pop();
                TreeNode left = node.left;
                TreeNode right = node.right;

                node.right = left;
                node.left = right;

                if (right != null) {
                    queue.add(right);
                }
                if (left != null) {
                    queue.add(left);
                }
            }
        }
        return root;
    }

    /**
     * 226丶反转二叉树
     * 递归，深度遍历，前序遍历
     */
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    /**
     * 101丶对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        return isSymmetricLeftRight(root.left, root.right);
    }

    private boolean isSymmetricLeftRight(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null) {
            return false;
        }
        if (right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }

        boolean a = isSymmetricLeftRight(left.left, right.right);
        boolean b = isSymmetricLeftRight(left.right, right.left);
        return a && b;
    }

    /**
     * 104丶二叉树的最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int a = maxDepth(root.left) + 1;
        int b = maxDepth(root.right) + 1;
        return Math.max(a, b);
    }

    /**
     * 111丶二叉树的最小深度
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int a = minDepth(root.left);
        int b = minDepth(root.right);

        if (root.left == null && root.right != null) {
            return b + 1;
        }
        if (root.right == null && root.left != null) {
            return a + 1;
        }

        return Math.min(a, b) + 1;
    }

    /**
     * 222丶完全二叉树的节点数量
     */
    public int countNodes(TreeNode root) {
        if (Objects.isNull(root)) {
            return 0;
        }

        int a = countNodes(root.left);
        int b = countNodes(root.right);
        return a + b + 1;
    }

    /**
     * 110丶平衡二叉树
     * 左右子树的高度差不能超过1
     */
    public boolean isBalanced(TreeNode root) {
        return h(root) != -1;
    }

    private int h(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int a = h(root.left);
        int b = h(root.right);
        if (a == -1 || b == -1) {
            return -1;
        }
        if (Math.abs(a - b) > 1) {
            return -1;
        }
        return Math.max(a, b) + 1;
    }


    /**
     * 257丶二叉树的所有路径
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        deal(list, root, "");
        return list;
    }

    private void deal(List<String> list, TreeNode root, String s) {
        if (root == null) {
            return;
        }

        String tmp = s + root.val;
        if (root.left == null && root.right == null) {
            list.add(tmp);
            return;
        }

        deal(list, root.left, tmp + "->");
        deal(list, root.right, tmp + "->");
    }


    /**
     * 404丶左叶子节点之和
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int a = sumOfLeftLeaves(root.left);
        int b = sumOfLeftLeaves(root.right);

        int val = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            val = root.left.val;
        }

        return a + b + val;
    }

    /**
     * 513丶找树左下角的值
     * 层序遍历
     */
    public int findBottomLeftValue(TreeNode root) {
        int leftMin = 0;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pop();
                if (i == 0) {
                    leftMin = node.val;
                }

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }

        return leftMin;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
